package com.klun.huiwen;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

public class huiwentest {

    public void findmaxhuiwen(String data){
        char[] chars = data.toCharArray();

        Stack chars1 = new Stack();
        Stack chars2 = new Stack();

        Character pre1 = new Character('0'); // 当前值得前1个
        Character pre2 = new Character('0'); // 当前值得前2个
        Character current = new Character('0');// 当前值

        boolean flag = false;

        if(chars.length <= 3){
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            char aChar = chars[i];
            if( i==0 ){
                pre2 =aChar;
                continue;
            }
            if( i==1 ){
                pre1 =aChar;
                continue;
            }
            if( i==2 ){
                current =aChar;
                continue;
            }

            if(flag){
                pre2 = pre1;
                pre1 = current;
                current = aChar;
            }

            /* 判断哪个不为空 */
            if(!chars1.empty()){

                /*开启回文*/
                if(current.equals(pre1)){
                    flag = true;
                }
                if(chars1.pop().equals(aChar)){

                }

                /* 放入当前值 */
                chars1.push(aChar);
            }
        }
    }

    /**
     * 判断最大的回文数 o(n3)
     * @param s
     * @return
     */
    public static String longestPalindrome3(String s){
        if(s.length() <= 1){
            return s;
        }
        for(int i = s.length();i>0;i--){//子串长度
            for (int j = 0; j < s.length() -i; j++) {
                String sub = s.substring(j,i+j);
                int count =0;//计数，用来判断是否对称
                for (int k = 0; k < sub.length()/2; k++) {
                    if(sub.charAt(k)==sub.charAt(sub.length()-k-1)){
                        count++;
                    }
                }
                if(count == sub.length()/2){
                    return sub;
                }
            }

        }
        return "";
    }

    /**
     * 最大回文子串的o(n2)的方法
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s){
        if(s.length() <= 1)return s;
        for(int i=0;i<s.length()-1;i++){
            findLongestPalindrome(s,i,i);
            findLongestPalindrome(s,i,i+1);
        }
        return sub;
    }
    private static int maxLen = 0;
    private static String sub = "";
    public static void findLongestPalindrome(String s,int low,int high){
        while (low >=0 && high <= s.length()-1){
            if(s.charAt(low) == s.charAt(high)){
                if(high - low+1>maxLen){
                    maxLen =high -low +1;
                    sub = s.substring(low,high+1);
                }
                low --;
                high ++;
            }else break;
        }
    }

    /**
     * 关于最长回文的最佳算法 Manacher 算法
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s){
        List<Character> s_new = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            s_new.add('#');
            s_new.add(s.charAt(i));
        }
        s_new.add('#');
        List<Integer> len =  new ArrayList<>();
        String sub = "";//最长回文子串
        int sub_midd = 0;// 表示在i之前所得到的len数组中的最大值所在位置
        int sub_side = 0;// 表示以sub_midd为中心的最长回文子串的最右端在s_new中的位置
        len.add(1);
        for (int i = 0; i < s_new.size(); i++) {
            /**
             * 处理上一轮循环所在的位置的的最右端
             */
            if(i<sub_side){ //i<sub_side时，在len[j]和sub-i中取最小值，省去了j的判断
                int j = 2*sub_midd - i; // 最大回文所在的位置 * 2 - 当前的遍历位置
                /**
                 * sub_side > i 并且 当前的最大回文长度 小于 sub_side - i
                 */
                if(j>=2*sub_midd - sub_side && len.get(i) <= sub_side-i){
                    len.add(len.get(j));
                } else {
                    len.add(sub_side -i +1);
                }
            }else { // i>= sub_side时，从头开始匹配
                len.add(1);
            }
            /**
             * i-len.get(i)>=0 : 如果遍历到的现在的值大于当前的回文串长度
             * i+len.get(i)<s_new.size() ： 并且 i+当前的回文长度 小于新字符串的长度
             * 然后回文左边 == 右边
             * 回文的最长长度+1
             */
            while ((i-len.get(i)>=0 && i+len.get(i)<s_new.size()) &&
                    (s_new.get(i-len.get(i)) == s_new.get(i+len.get(i)))){
                len.set(i,len.get(i)+1);// s_new[i]两端开始匹配，直到匹配失败停止
            }
            /**
             * len.get(sub_midd) ： sub_midd 最大回文所在的位置
             */
            if(len.get(i) >= len.get(sub_midd)){//匹配的新回文子串长度大于原有的长度
                sub_side = len.get(i)+i-1;
                sub_midd = i;
            }
        }
        sub = s.substring((2*sub_midd-sub_side)/2,sub_side/2);//再s中找到最长回文子串的位置
        return sub;
    }

    public static void main(String[] args) {
        StringBuffer s = generateString(new Random(),SOURCES,500000);
        String a = s.toString();
        // 逆序s
        String b = s.reverse().toString();
        String ss = (a + b).replace(" ","");
        long l = System.currentTimeMillis();
        String s1 = longestPalindrome1(ss);
        System.out.println(System.currentTimeMillis() - l);
        //System.out.println(s1);
        String s2 = longestPalindrome2(ss);
        System.out.println(System.currentTimeMillis() - l);
        //System.out.println(s2);
        String s3 = longestPalindrome3(ss);
        System.out.println(System.currentTimeMillis() - l);
//        System.out.println(s3);
        System.out.println();
    }

    public static final String SOURCES =
            "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";
    /**
     * Generate a random string.
     * @return
     */
    public static StringBuffer generateString(Random random ,String characters ,int length) {
        char[] text = new char[length];
        for (int i = 0; i < length; i++) {
            text[i] = characters.charAt(random.nextInt(characters.length()));
        }
        return new StringBuffer(new String(text));
    }
}
